package lib

//link to 875 1011 1231
func init() {
	Probs = append(Probs, Problem{
		Num:         410,
		Discription: "分割成k个子数组，使得每个子数组的和的最大值最小",
		Level:       3,
		Labels: map[string]int{
			"二分查找": 1,
			"单调函数二分":   1,
		},
	})
}

func SplitArray(nums []int, k int) int {
	//在子数组最大和<=maxSum的限定下，能否能分成<=k个子数组
	canSplit := func(maxSum int) bool {
		curSum := 0
		count := 0
		for _, val := range nums {
			if curSum+val > maxSum {
				count++
				curSum = 0
			}
			curSum += val
		}

		if curSum > 0 {
			count++
		}

		//如果切分的子数组数量<k，进一步切分肯定也满足子数组之和的最大值<=maxSum的条件
		return count <= k
	}

	//最大和的最小情况是单个拆分后，值最大的那个
	left := nums[0]
	//最大的情况是所有加在一起
	right := nums[0]
	for left < right {
		mid := left + (right-left)/2
		if canSplit(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}